"""
2286. 以组为单位订音乐会的门票
困难
相关标签
premium lock icon
相关企业
提示
一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：

#gather:同一组的 k 位观众坐在 同一排座位，且座位连续 。
#scatter:k 位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。
由于观众非常挑剔，所以：

只有当一个组里所有成员座位的排数都 小于等于 maxRow ，这个组才能订座位。每一组的 maxRow 可能 不同 。
如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
请你实现 BookMyShow 类：

BookMyShow(int n, int m) ，初始化对象，n 是排数，m 是每一排的座位数。
int[] gather(int k, int maxRow) 返回长度为 2 的数组，表示 k 个成员中 第一个座位 的排数和座位编号，这 k 位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的 r 和 c 满足第 r 排中 [c, c + k - 1] 的座位都是空的，且 r <= maxRow 。如果 无法 安排座位，返回 [] 。
boolean scatter(int k, int maxRow) 如果组里所有 k 个成员 不一定 要坐在一起的前提下，都能在第 0 排到第 maxRow 排之间找到座位，那么请返回 true 。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有 k 个成员的座位，请返回 false 。


示例 1：

输入：
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
输出：
[null, [0, 0], [], true, false]

解释：
BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。
bms.gather(4, 0); // 返回 [0, 0]
                  // 这一组安排第 0 排 [0, 3] 的座位。
bms.gather(2, 0); // 返回 []
                  // 第 0 排只剩下 1 个座位。
                  // 所以无法安排 2 个连续座位。
bms.scatter(5, 1); // 返回 True
                   // 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。
bms.scatter(5, 1); // 返回 False
                   // 总共只剩下 1 个座位。


提示：

1 <= n <= 5 * 104
1 <= m, k <= 109
0 <= maxRow <= n - 1
gather 和 scatter 总 调用次数不超过 5 * 104 次。
"""
from typing import List



class BookMyShow:
    """
    这里的和普通线段树区别：一排作为一个元素，每排的元素是当前排剩下的连续座位数量，对于gather就是找最值，而对于scatter则是有作为就行，找最前的直到座位数量和=k
    """
    def __init__(self, n: int, m: int):
        # arr = [m] * n
        self._n = n
        self._m = m
        self._l = 2 << (n - 1).bit_length()
        arr = [0] * (self._l//2)
        for i in range(n):
            arr[i] = m
        print(arr)
        self._tree = [0] * self._l
        self._build(arr, 1, 0, len(arr) - 1)
        print(self._tree)
    # 合并两个 val
    def _merge_val(self, a: int, b: int) -> int:
        return max(a, b)  # **根据题目修改**

    # 合并左右儿子的 val 到当前节点的 val
    def _maintain(self, node: int) -> None:
        self._tree[node] = self._merge_val(self._tree[node * 2], self._tree[node * 2 + 1])

    # 用 a 初始化线段树
    # 时间复杂度 O(n)
    def _build(self, a: List[int], node: int, l: int, r: int) -> None:
        if l == r:  # 叶子
            self._tree[node] = a[l]  # 初始化叶节点的值
            return
        m = (l + r) // 2
        self._build(a, node * 2, l, m)  # 初始化左子树
        self._build(a, node * 2 + 1, m + 1, r)  # 初始化右子树
        self._maintain(node)
    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        """
        寻找ql,qr区间的最大值(未实现找第一个>=x的功能)，node,l,r只是内部递归使用，不作为传参
        :param node:
        :param l:
        :param r:
        :param ql:
        :param qr:
        :return:
        """
        #不一定需要完全遍历到叶子节点，比如当前计算的是数组的最大值，比如[3,4,1]那么直接首次返回顶点4即可，不需要遍历到叶子，因为4下面的所有叶子都包含在[ql,qr]
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内，返回当前的就是最大值
            return self._tree[node]
        m = (l + r) // 2
        #分了一半，但是发现要查找的元素全在左边
        if qr <= m:  # [ql, qr] 在左子树
            return self._query(node * 2, l, m, ql, qr)
        #分了一半，但是发现要查找的元素全在右
        if ql > m:  # [ql, qr] 在右子树
            return self._query(node * 2 + 1, m + 1, r, ql, qr)
        #左右树都存在寻找的位置，找个最大的
        l_res = self._query(node * 2, l, m, ql, qr)
        r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
        return self._merge_val(l_res, r_res)
    # 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    # 时间复杂度 O(log n)
    def query(self, ql: int, qr: int) -> int:
        return self._query(1, 0, self._n - 1, ql, qr)
    def get(self, i: int) -> int:
        return self._query(1, 0, self._n - 1, i, i)
    def _querFirstLarge(self, node: int, l: int, r: int, ql: int, qr: int,target: int) -> int:
        """
        找到ql,qr区间第一个>=target的数
        :param node:
        :param l:
        :param r:
        :param ql:
        :param qr:
        :param target:
        :return:
        """
        #如果当前最大还小，直接返回
        if self._tree[node]<target:
            return -1
        #遍历到叶子节点
        if l==r:
            self._tree[node] = self._tree[node] - target #减去当前座位
            return l
        m = (l+r)//2
        #分了一半，但是发现要查找的元素全在左边
        if qr <= m:  # [ql, qr] 在左子树
            return self._querFirstLarge(node * 2, l, m, ql, qr,target)
        #分了一半，但是发现要查找的元素全在右
        if ql > m:  # [ql, qr] 在右子树
            return self._querFirstLarge(node * 2 + 1, m + 1, r, ql, qr,target)
        #优先找左边,如果左边找得到就不需要找右边了
        res = self._querFirstLarge(node * 2, l, m, ql, qr,target)
        if res == -1:
            #左边没找到找右边
            res = self._querFirstLarge(node * 2+1, m+1, r, ql, qr,target)
        #如果不能重复拿同一个数字,则需要更新当前的最大值
        self._maintain(node)
        return res
    def gather(self, k: int, maxRow: int) -> List[int]:
        #找一个最先的<=maxRow，超过k的最大值
        res = self._querFirstLarge(1, 0, self._n - 1, 0, maxRow, k)
        #找不到，返回-1
        if res==-1:
            return []
        remain = self.get(res)
        return [res,self._m - remain - k]
    def _querScatter(self, node: int, l: int, r: int, ql: int, qr: int,target: int) -> int:
        """
        找到ql,qr区间第一个>=target的数
        :param node:
        :param l:
        :param r:
        :param ql:
        :param qr:
        :param target:
        :return:
        """
        #遍历到叶子节点
        if l==r:
            if target>=self._tree[node]:
                target -= self._tree[node]
                self._tree[node] = 0
            else:
                self._tree[node] = self._tree[node] - target
                target=0
            return target
        m = (l+r)//2
        #分了一半，但是发现要查找的元素全在左边
        if qr <= m:  # [ql, qr] 在左子树
            return self._querScatter(node * 2, l, m, ql, qr,target)
        #分了一半，但是发现要查找的元素全在右
        if ql > m:  # [ql, qr] 在右子树
            return self._querScatter(node * 2 + 1, m + 1, r, ql, qr,target)
        #优先找左边,如果左边找得到就不需要找右边了
        target = self._querScatter(node * 2, l, m, ql, qr,target)
        if target > 0:
            #左边没找到找右边
            target = self._querScatter(node * 2+1, m+1, r, ql, qr,target)
        #如果不能重复拿同一个数字,则需要更新当前的最大值
        self._maintain(node)
        return target
    def scatter(self, k: int, maxRow: int) -> bool:
        #判断
        tree = self._tree
        remain = 0
        for i in range(self._l//2,self._l//2 + maxRow + 1):
            remain+=tree[i]
        if remain>=k:
            self._querScatter(1, 0, self._n - 1, 0, maxRow, k)
            return True
        else:
            return False

if __name__ == '__main__':
    # BookMyShow(5, 9) - 初始化对象，5排座位，每排9个座位
    bms = BookMyShow_res1(5, 9)
    print("BookMyShow(5, 9) - initialized")

    # gather(10, 1) - 尝试在同一排连续安排10个座位，限制在第0-1排
    result1 = bms.gather(10, 1)
    print(f"gather(10, 1) = {result1}")

    # scatter(3, 3) - 尝试分散安排3个座位，可以在第0-3排之间
    result2 = bms.scatter(3, 3)
    print(f"scatter(3, 3) = {result2}")

    # gather(9, 1) - 尝试在同一排连续安排9个座位，限制在第0-1排
    result3 = bms.gather(9, 1)
    print(f"gather(9, 1) = {result3}")

    # gather(10, 2) - 尝试在同一排连续安排10个座位，限制在第0-2排
    result4 = bms.gather(10, 2)
    print(f"gather(10, 2) = {result4}")

    # gather(2, 0) - 尝试在同一排连续安排2个座位，限制在第0排
    result5 = bms.gather(2, 0)
    print(f"gather(2, 0) = {result5}")
class BookMyShow_res1:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        self.min = [0] * (2 << n.bit_length())  # 相比 4n 空间更小
        self.sum = [0] * (2 << n.bit_length())

    # 线段树：把下标 i 上的元素值增加 val
    def update(self, o: int, l: int, r: int, i: int, val: int) -> None:
        if l == r:
            self.min[o] += val
            self.sum[o] += val
            return
        m = (l + r) // 2
        if i <= m:
            self.update(o * 2, l, m, i, val)
        else:
            self.update(o * 2 + 1, m + 1, r, i, val)
        self.min[o] = min(self.min[o * 2], self.min[o * 2 + 1])
        self.sum[o] = self.sum[o * 2] + self.sum[o * 2 + 1]

    # 线段树：返回区间 [L,R] 内的元素和
    def query_sum(self, o: int, l: int, r: int, L: int, R: int) -> int:
        if L <= l and r <= R:
            return self.sum[o]
        res = 0
        m = (l + r) // 2
        if L <= m:
            res = self.query_sum(o * 2, l, m, L, R)
        if R > m:
            res += self.query_sum(o * 2 + 1, m + 1, r, L, R)
        return res

    # 线段树：返回区间 [0,R] 中 <= val 的最靠左的位置，不存在时返回 -1
    def find_first(self, o: int, l: int, r: int, R: int, val: int) -> int:
        if self.min[o] > val:
            return -1  # 整个区间的元素值都大于 val
        if l == r:
            return l
        m = (l + r) // 2
        if self.min[o * 2] <= val:
            return self.find_first(o * 2, l, m, R, val)
        if R > m:
            return self.find_first(o * 2 + 1, m + 1, r, R, val)
        return -1

    def gather(self, k: int, maxRow: int) -> List[int]:
        # 找第一个能倒入 k 升水的水桶
        r = self.find_first(1, 0, self.n - 1, maxRow, self.m - k)
        if r < 0:  # 没有这样的水桶
            return []
        c = self.query_sum(1, 0, self.n - 1, r, r)
        self.update(1, 0, self.n - 1, r, k)  # 倒水
        return [r, c]

    def scatter(self, k: int, maxRow: int) -> bool:
        # [0,maxRow] 的接水量之和
        s = self.query_sum(1, 0, self.n - 1, 0, maxRow)
        if s > self.m * (maxRow + 1) - k:
            return False  # 水桶已经装了太多的水
        # 从第一个没有装满的水桶开始
        i = self.find_first(1, 0, self.n - 1, maxRow, self.m - 1)
        while k:
            left = min(self.m - self.query_sum(1, 0, self.n - 1, i, i), k)
            self.update(1, 0, self.n - 1, i, left)  # 倒水
            k -= left
            i += 1
        return True